package 力扣链表;

public class Leedcode83删除排序链表中的重复元素 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(3,null);
        ListNode node4 = new ListNode(3,node5);
        ListNode node3 = new ListNode(2,node4);
        ListNode node2 = new ListNode(1,node3);
        ListNode node1 = new ListNode(1,node2);
        ListNode node = deleteDuplicates(node1);
        while (node != null){
            System.out.println(node.val);
            node = node.next;
        }
    }
    //双指针法
    public static ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode prev = head;
        ListNode cur = prev.next;
        while (cur != null){
            //如果prev和cur不相等，则prev和cur都后移
            if (prev.val != cur.val){
                prev = prev.next;
                cur = cur.next;
            }else {
                //如果prev和cur相等，cur后移
                while (cur != null && prev.val == cur.val){
                    cur =cur.next;
                }
                //此时，cur和prev不相等，如果cur等于null；prev.next = cur ; 如果不等于空，prev.next = cur;
                prev.next = cur;
                if (cur != null){
                    prev = prev.next;
                    cur = cur.next;
                }
            }
        }
        return head;
    }

    //双指针优化
    public static ListNode deleteDuplicates2(ListNode head) {
        //如果head只有一个节点或者head为空，直接返回
        if (head == null || head.next == null){
            return head;
        }
        //走到这一步，说明head至少有两个节点，让prev指向当前节点的头，让cur指向当前节点的下一个节点
        ListNode prev = head;
        ListNode cur = prev.next;
        //终止条件，如果cur等于空，说明此时已经到链表的最后一个节点，循环结束，返回链表的头节点
        while (cur != null){
            //如果prev和cur不相等，则prev和cur都后移
            if (prev.val != cur.val){
                prev = prev.next;
            //如果prev和cur相等，则让prev的next指向cur的next，在让cur后移一位，开始第二次循环，
            }else {
                prev.next = cur.next;
            }
            cur = cur.next;
        }
        //走到这里说明
        return head;
    }

    //递归解法
    /**
     * 方法的作用：此方法的作用是，传入一个头节点，我就可以删除这个链表中所有的重复节点
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        //1.先找递归终止条件
        //如果链表为空，或者链表只有一个节点，直接返回
        if (head == null || head.next == null){
            return head;
        }
        //走到这里说明链表最少有两个节点，我只知道当前节点，其他节点并不知道，所以，再次需要判断其他节点的val和当前节点的值是否相等
        //如果head.val == newHead.val(剩余节点返回的节点) ，就让head.next = newHead.next;
        ListNode newHead = deleteDuplicates(head.next);
        //如果相等，则说明当前节点和剩余链表返回的头节点相等，
        if (head.val == newHead.val){
            head.next = newHead.next;
        //如果不相等，则将当前节点的next指向剩余链表的头节点
        }else {
            head.next = newHead;
        }
        return head;
    }
}

